import java.util.Stack;

class Demo {

    static boolean isOpen (char c) {
	return c == '(' || c == '{';
    }
    static boolean isClose (char c) {
	return c == ')' || c == '}';
    }
    static boolean matchingBracket (char open, char close) {
	return open == '(' && close == ')' || open == '{' && close == '}';
    }

    static boolean isBalanced(String s) {
	Stack stk = new Stack();
	for (int i = 0; i < s.length(); i++) {
	    char sym = s.charAt(i);
	    if (isOpen(sym))
		stk.push(new Character(sym));
	    else if (isClose(sym)) {
		if (stk.empty())
		    return false;
		char open = ((Character)(stk.pop())).charValue();
		if (!matchingBracket(open, sym))
		    return false;
	    }
	}
	return stk.empty();
    }

    public static void main (String[] args) {
	System.out.print("The string " + args[0]);
	if (isBalanced(args[0]))
	    System.out.println(" is balanced");
	else
	    System.out.println(" is not balanced");
	/*
	System.out.println("() " + isBalanced("()"));
	System.out.println("({)} " + isBalanced("({)}"));
	System.out.println("(()()){} " + isBalanced("(()()){}"));
	*/
    }
}